import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/25 9:02
 * @description 将有向图DFS + 回溯
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] graph = {{4, 3, 1}, {3, 2, 4}, {3}, {4}, {}};
        solution.allPathsSourceTarget(graph);
    }

    private int n;

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        n = graph.length;
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        temp.add(0);
        dfs(graph, 0, n - 1, ans, temp);
        return ans;
    }

    public void dfs(int[][] graph, int x, int end, List<List<Integer>> ans, List<Integer> temp) {
        if (x == end) {
            // 注意这里需要new一份，不然temp变，ans也会变
            ans.add(new ArrayList<>(temp));
            return;
        }
        for (int y : graph[x]) {
            temp.add(y);
            dfs(graph, y, n - 1, ans, temp);
            temp.remove(temp.size() - 1);
        }
    }
}
